package 二叉树.基础;

import java.util.ArrayList;
import java.util.List;

public class Traversa {
    private static TreeNode root;

    TreeNode creatTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        root = A;
        return root;
    }

    //先序遍历
    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //先序遍历，将返回值存储到list中
    //一种写法，缺点没有充分使用返回值
    List<TreeNode> list = new ArrayList<>();

    public List<TreeNode> preOrder1(TreeNode root) {
        if (root == null) {
            return list;
        }
        list.add(root);
        preOrder1(root.left);
        preOrder1(root.right);
        return list;
    }

    //第二种写法
    public List<TreeNode> preOrder2(TreeNode root) {
        List<TreeNode> list1 = new ArrayList<>();
        if (root == null) {
            return list1;
        }
        list1.add(root);
        List<TreeNode> leftList = preOrder2(root.left);
        list1.addAll(leftList);
        List<TreeNode> rightList = preOrder2(root.right);
        list1.addAll(rightList);
        return list1;
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public List<TreeNode> inOrder2(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<TreeNode> leftlist = inOrder2(root.left);
        list.addAll(leftlist);
        list.add(root);
        List<TreeNode> rightlist = inOrder2(root.right);
        list.addAll(rightlist);
        return list;
    }

    //后续遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public List<TreeNode> postOrder2(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<TreeNode> leftList = postOrder2(root.left);
        list.addAll(leftList);
        List<TreeNode> rightList = postOrder2(root.right);
        list.addAll(rightList);
        list.add(root);
        return list;
    }

    public static void main(String[] args) {
        Traversa myTree = new Traversa();
        myTree.creatTree();
        //先序遍历的使用
        myTree.preOrder(root);
        System.out.println();
        //得到的是地址，值需要遍历输出
        List<TreeNode> ret  =  myTree.preOrder2(root);
        for(TreeNode x:ret){
            System.out.print(x.val+" ");
        }
        System.out.println();
        System.out.println("=====");
        //中序遍历
        myTree.inOrder(root);
        System.out.println();
        List<TreeNode> ret1 = myTree.inOrder2(root);
        for(TreeNode x:ret1){
            System.out.print(x.val+" ");
        }
        System.out.println();
        System.out.println("=====");
        //后序遍历
        myTree.postOrder(root);
        System.out.println();
        List<TreeNode> ret2 = myTree.postOrder2(root);
        for(TreeNode x:ret2){
            System.out.print(x.val+" ");
        }
        System.out.println();
        System.out.println("=====");


    }


}
